<?php
/**
 * Created by PhpStorm.
 * User: admin
 * Date: 2019/1/10
 * Time: 10:23
 */

//变体一：查找第一个值等于给定值的元素
function searchFirstVal($arrData, $val)
{
    $len= count($arrData);
    $low = 0;
    $high = $len-1;
    while ($low <= $high){
        $mid = (int)(($low+$high)/2);
        if($arrData[$mid] > $val){
            $high = $mid-1;
        }elseif ($arrData[$mid] < $val){
            $low = $mid+1;
        }else{
            if($mid == 0 || $arrData[$mid-1]<$val){
                return $mid;
            }else{
                $high= $mid -1;
            }
        }
    }
    return -1;
}

//变体二 查找最后一个等与给定值的元素
function searchLastVal($arrData, $val)
{
    $len = count($arrData);
    $low = 0;
    $high = $len -1;
    while($low <= $high){
        $mid = (int)(($low+$high)/2);
        if($arrData[$mid] > $val){
            $high = $mid-1;
        }elseif ($arrData[$mid] < $val){
            $low = $mid+1;
        }else{
            if($mid == ($len -1) || $arrData[$mid+1] > $val ){
                return $mid;
            }else{
                $low = $mid+1;
            }
        }
    }
    return -1;
}

//变体三 查找第一个大于给定值的元素
function searchFirstGreaterThan($arrData, $val)
{
    $len = count($arrData);
    $high = $len-1;
    $low = 0;
    while($low<=$high){
        $mid = (int)(($low+$high)/2);
        if($arrData[$mid] <= $val){
            $low = $mid+1;
        }else{
            if($mid == 0 || $arrData[$mid-1] <= $val){
                return $mid;
            }else{
                $high = $mid-1;
            }
        }
    }
    return -1;
}

//变体四 查找最后一个 小于等于给定值的元素
function searchLastLessThan($arrData, $val)
{
    $len = count($arrData) -1;
    $low = 0;
    $high = $len;
    while ($low<=$high){
        $mid = (int)(($low+$high)/2);
        if($arrData[$mid] > $val){
            $high = $mid-1;
        }else{
            if($mid ==$len ||$arrData[$mid+1]>$val){
                return $mid;
            }else{
                $low = $mid+1;
            }
        }
    }
    return -1;

}



$arrData = [1,2,4,5,6,8,8,8,11,18];
//变体一
echo "1".PHP_EOL;
var_dump(searchFirstVal($arrData, 8));
var_dump(searchFirstVal($arrData, 9));

//变体二
echo "2".PHP_EOL;
var_dump(searchLastVal($arrData, 8));
var_dump(searchLastVal($arrData, 9));

//变体三
echo "3".PHP_EOL;
var_dump(searchFirstGreaterThan($arrData, 0));
var_dump(searchFirstGreaterThan($arrData, 8));
var_dump(searchFirstGreaterThan($arrData, 7));
var_dump(searchFirstGreaterThan($arrData, 20));

//变体四
echo "4".PHP_EOL;
var_dump(searchLastLessThan($arrData, 0));
var_dump(searchLastLessThan($arrData, 8));
var_dump(searchLastLessThan($arrData, 7));
var_dump(searchLastLessThan($arrData, 20));

